package com.hy.greedy;

public class SwingSeq {

    /**
     * 376. 摆动序列
     * 力扣题目链接
     *
     * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
     *
     * 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
     *
     * 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
     *
     * 示例 2:
     *
     * 输入: [1,17,5,10,13,15,10,5,16,8]
     * 输出: 7
     * 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
     *
     *  思路1（贪心解法）
     * 本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
     *
     * 相信这么一说吓退不少同学，这要求最大摆动序列又可以修改数组，这得如何修改呢？
     *
     * 来分析一下，要求删除元素使其达到最大摆动序列，应该删除什么元素呢？
     *
     * 用示例二来举例，如图所示：
     *
     * 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
     *
     * 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
     *
     * @param num
     * @return
     */

    public int countSwingSeq(int [] num){
        //当前差值
        int curDiff = 0;
        // 上一个 差值
        int preDiff = 0;
        int count = 1;
        for (int i = 1; i < num.length; i++) {
            // 当前差值
            curDiff = num[i] - num[i-1];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff >= 0 && preDiff <= 0) || (curDiff <= 0 && preDiff >= 0)){
                preDiff = curDiff;
                count ++;
            }
        }
        return count;
    }

    public int wiggleMaxLength(int [] num){
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        int dp [][] = new int[num.length][2];
        dp[0][0] = dp[0][1] = 1;
        for (int i = 0; i < num.length; i++) {
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; j++) {
                if (num[j] > num[i]){
                    // i 是 波谷
                    dp[i][1] = Math.max(dp[i][1],dp[j][0] + 1);
                }
                if (num[j] < num[i]){
                    // i 是 波峰
                    dp[i][0] = Math.max(dp[i][0],dp[j][1] + 1);
                }
            }
        }
        return Math.max(dp[num.length - 1][0],dp[num.length - 1][1]);
    }



    public static void main(String[] args) {
        int [] num = {1,17,5,10,13,15,10,5,16,8};
        SwingSeq swingSeq = new SwingSeq();
        System.out.println("res: "+ swingSeq.countSwingSeq(num));
        System.out.println("res: "+ swingSeq.wiggleMaxLength(num));
    }
}
